|
In multithreaded computing, the ABA problem occurs during synchronization, when a location is read twice, has the same value for both reads, and "value is the same" is used to indicate "nothing has changed". However, another thread can execute between the two reads and change the value, do other work, then change the value back, thus fooling the first thread into thinking "nothing has changed" even though the second thread did work that violates that assumption. The ABA problem occurs when multiple threads (or processes) accessing shared memory interleave. Below is the sequence of events that will result in the ABA problem: * Process reads value A from shared memory, * is preempted, allowing process to run, * modifies the shared memory value A to value B and back to A before preemption, * begins execution again, sees that the shared memory value has not changed and continues. Although can continue executing, it is possible that the behavior will not be correct due to the "hidden" modification in shared memory. A common case of the ABA problem is encountered when implementing a lock-free data structure. If an item is removed from the list, deleted, and then a new item is allocated and added to the list, it is common for the allocated object to be at the same location as the deleted object due to optimization. A pointer to the new item is thus sometimes equal to a pointer to the old item which is an ABA problem. == Examples == :Natalie is waiting in her car at a red traffic light with her children. Her children start fighting with each other while waiting, and she leans back to scold them. Once their fighting stops, Natalie checks the light again and notices that it's still red. However, while she was focusing on her children, the light had changed to green, and then back again. Natalie doesn't think the light ever changed, but the people waiting behind her are very mad and honking their horns now. In this scenario, the 'A' state is when the traffic light is red, and the 'B' state is when it's green. Originally, the traffic light starts in 'A' state. If Natalie looked at the light she would have noticed the change. But she only looked when the light was red (state 'A'). There is no way to tell if the light turned green during the time of no observation. Consider a software example of ABA using a lock-free stack: / * Naive lock-free stack which suffers from ABA problem. */ class Stack } // // Pushes the object specified by obj_ptr to stack. // void Push(Obj * obj_ptr) } }; This code can normally prevent problems from concurrent access, but suffers from ABA problems. Consider the following sequence: Stack initially contains ''top'' → A → B → C Thread 1 starts running pop: ret = A; next = B; Thread 1 gets interrupted just before the compare_exchange_weak... // Now the stack is top → B → C // Now the stack is top → C delete B; Now the stack is ''top'' → A → C When Thread 1 resumes: compare_exchange_weak(A, B) This instruction succeeds because it finds ''top'' == ret (both are A), so it sets top to next (which is B). As B has been deleted the program will access freed memory when it tries to look the first element on the stack. In C++, as shown here, accessing freed memory is undefined behavior: this may result in crashes, data corruption or even just silently appear to work correctly. ABA bugs, such as this, can be difficult to debug. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ABA problem」の詳細全文を読む スポンサード リンク
|